package com.example.leetcode.tree;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
 *
 * 数据范围：输入二叉树的节点数
 * 0
 * ≤
 * 𝑛
 * ≤
 * 1000
 * 0≤n≤1000，二叉树中每个节点的值
 * 0
 * ≤
 * 𝑣
 * 𝑎
 * 𝑙
 * ≤
 * 1000
 * 0≤val≤1000
 * 要求：空间复杂度
 * 𝑂
 * (
 * 1
 * )
 * O(1)（即在原树上操作），时间复杂度
 * 𝑂
 * (
 * 𝑛
 * )
 * O(n)
 *
 * 注意:
 * 1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
 * 2.返回链表中的第一个节点的指针
 * 3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
 * 4.你不用输出双向链表，程序会根据你的返回值自动打印输出
 * 输入描述：
 * 二叉树的根节点
 * 返回值描述：
 * 双向链表的其中一个头节点。
 *
 *
 * 输入：
 * {10,6,14,4,8,12,16}
 * 复制
 * 返回值：
 * From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
 * 复制
 * 说明：
 * 输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。
 *
 */
public class Tree2 {
    public static void main(String[] args) {
        TreeNode pRootOfTree1 = new TreeNode(10);
        TreeNode pRootOfTree2 = new TreeNode(6);
        TreeNode pRootOfTree3 = new TreeNode(14);
        pRootOfTree1.left =pRootOfTree2;
        pRootOfTree1.right =pRootOfTree3;

        TreeNode pRootOfTree4 = new TreeNode(4);
        TreeNode pRootOfTree5 = new TreeNode(8);
        pRootOfTree2.left = pRootOfTree4;
        pRootOfTree2.right = pRootOfTree5;


        TreeNode pRootOfTree6 = new TreeNode(12);
        TreeNode pRootOfTree7 = new TreeNode(16);
        pRootOfTree3.left = pRootOfTree6;
        pRootOfTree3.right = pRootOfTree7;

        Tree2 tree2 = new Tree2();
        tree2.Convert(pRootOfTree1);
    }

    TreeNode head = null;
    TreeNode pre = null;

    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }

        Convert(pRootOfTree.left);
        if(pre == null) {
            pre = pRootOfTree;
            head = pRootOfTree;
        } else {
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }
}
